/*
 * @lc app=leetcode.cn id=704 lang=typescript
 *
 * [704] 二分查找
 */

// @lc code=start

//  思想：二分查找
//  注意细节，参考：https://labuladong.github.io/algo/2/21/55/

//  复杂度：O(logn) O(1)

function search(nums: number[], target: number): number {
    let left = 0, right = nums.length - 1

    while (left <= right) {
        const mid = Math.floor(left + (right - left) / 2)
        if (nums[mid] == target) {
            return mid
        } else if (nums[mid] < target) {
            left = mid + 1
        } else if (nums[mid] > target) {
            right = mid - 1
        }
    }
    return -1
};
// @lc code=end

console.log(search([-1, 0, 3, 5, 9, 12], 9))  // 4
console.log(search([-1, 0, 3, 5, 9, 12], 2))  // -1
